package com.le.medium.class7;

import org.junit.Test;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 给定一个整数数组A，长度为n，有 1 <= A[i] <= n，且对于[1,n]的整数，其 中部分整数会重复出现而部分不会出现。
 * 实现算法找到[1,n]中所有未出现在A中的整数。
 * 提示：尝试实现O(n)的时间复杂度和O(1)的空间复杂度（返回值不计入空间复杂度）。
 * 输入描述： 一行数字，全部为整数，空格分隔 A0 A1 A2 A3...
 * 输出描述： 一行数字，全部为整数，空格分隔R0 R1 R2 R3...
 * 示例1:
 * 输入 1 3 4 3
 * 输出 2
 */
public class Problem02_PrintNoInArray {

    // 空间复杂度O(n)
    public static void printNumberNoInArray(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        int n = arr.length;
        Set<Integer> set = new HashSet<>();
        for (int i = 1; i < n + 1; i++) {
            set.add(i);
        }
        Set<Integer> s = new HashSet<>();
        for (int i = 0; i < n; i++) {
            s.add(arr[i]);
        }
        set.forEach(p -> {
            if (!s.contains(p)) {
                System.out.print(p + " ");
            }
        });
    }

    // 空间复杂度O(n) 建立1--n每个元素出现次数的词频表
    public static void printNumberNoInArray2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        int n = arr.length;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 1; i < n + 1; i++) {
            map.put(i, 0);
        }
        for (int i = 0; i < n; i++) {
            if (map.containsKey(arr[i])){
                map.put(arr[i], map.get(arr[i]) + 1);
            }
        }
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() == 0){
                System.out.print(entry.getKey()+ " ");
            }
        }
    }

    // 空间复杂度O(1)
    // 保证i位置存放的是i+1元素的值
    // 即所有i位置的值不等于i+1则是未出现过得元素
    public static void printNumberNoInArray3(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            modify(arr[i], arr);
        }
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != i + 1) {
                System.out.print((i + 1) + " ");
            }
        }
    }

    public static void modify(int value, int[] arr) {
        while (arr[value - 1] != value) {
            int tmp = arr[value - 1];
            arr[value - 1] = value;
            value = tmp;
        }
    }

    @Test
    public void test() {
        int[] test = {3, 2, 3, 5, 6, 1, 6};
        printNumberNoInArray(test);
        System.out.println();
        printNumberNoInArray2(test);
        System.out.println();
        printNumberNoInArray3(test);
    }
}
